/**
 * Created with IntelliJ IDEA.
 * Description:最长回文子串
 * User: 86183
 * Date: 2023-05-05
 * Time: 9:41
 */
public class Task03 {
    public String longestPalidrome(String s){
        if(s.length() <= 1){
            return s;
        }
        int max = 1;
        int begin = 0;
        boolean[][] dp = new  boolean[s.length()][s.length()];
        char[] a = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if(a[i] != a[j]){
                    dp[i][j] = false;
                }else {
                    if(j-i < 2){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1 > max){
                    max = j - i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+max);
    }
}
